COMMENT ⊗   VALID 00028 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	.<<last label: P1>>
C00004 00003	.SEC(Introduction,,,P1:)
C00013 00004	.SS(Simple computers)
C00035 00005	.Sec(LISP)
C00037 00006	.Ss(LISP data structures)
C00040 00007	.ss(LISP operations)
C00054 00008
C00058 00009	Besides decomposing lists, we should expect to build new  ones.
C00064 00010	.SS(Definitions and variables)
C00068 00011	.SS(Predicates)
C00072 00012	.ss(Conditional expressions)
C00079 00013	.ss(Extended examples)
C00102 00014	.SS(Summary and preview)
C00107 00015	We close with a preview of coming events.
C00114 00016	.BEGIN VERBATIM
C00118 00017	.SS(Symbolic mathematics)
C00136 00018	.<<abstracting from rep>>
C00148 00019	.SS(Tree Searching)
C00164 00020	.SS(Operating Systems and Language Systems)
C00171 00021	.SS(Data Bases)
C00172 00022	.SEC(OUTLINE)
C00173 00023	       II
C00174 00024	     III
C00175 00025	      IV
C00176 00026	      V
C00177 00027	      VI
C00178 00028	.END "VERB"
C00179 ENDMK
C⊗;
.<<last label: P1>>
.turn on "#";
.GROUP SKIP 12;
.BEGIN CENTER;
LECTURES ON LISP
by
John  Allen

copyright %fc%1 1977 by John Allen
.end
.SEC(Introduction,,,P1:)
This is the first installment in a series of six articles
on LISP. The final section of this paper outlines the five remaining pieces.
This initial paper explains and dispells some of the mystique surrounding
LISP-ish ideas.
LISP is simple and difficult, elegant and ad#hoc; it is a beautiful blend
of foresight and fortuity. LISP is a programming language, typically characterized
as a "special purpose list-processing language". But LISP is no more a special
purpose programming language than mathematics is a "special purpose
language for floating-point computations". LISP is also a precise
notation for describing general computations. We will treat both aspects of LISP:
its programming progerties as implemented on specific machines, and its properties
as a descriptive language for expressing algorithms.
Most of our emphasis will be on the implemented
aspects of LISP since that is what constitutes the programming 
language⊗↓These articles are condensed from ⊗↑[All#78]↑; that
book fills in many of the gaps in these articles. That book also discusses
more advanced topics, as well as more detailed information on
LISP implementations.←;
however, just as there's more to
mathematics than the accounting and bookeeping properties presented
in simple assembly language, there's much more to LISP
than "just another programming language".



We will use LISP to develop
 editors,
interpreters, compilers, and operating systems, as well as LISP itself.
We will use LISP to describe
 numerical computations and logical operations necessary to
endeavors as diverse as game playing, symbolic mathematics, 
 and scientific calculations.
Our path may be a bit more difficult
in spots than the more traditional assembly language approach, 
but its length is significantly shorter.
From our unique vantage point we will have a much clearer
view of the techniques and tools of the field.
The intent of structured programming and modular
programing will become more clear. 
Along the way we will 
implement LISP and that process will introduce
a whole host of tricks, tools and techniques, sufficient to satisfy
even the most jaded of programming palates.
 Later
our perspective will simplify the "mathematical" aspects of the
field --the mathematical theory of computation--: the correctness and
equivalence of progams. 
Sound interesting? It is!
.SS(Simple computers)

"in the beginning was the Word"  
.BEGIN TURN ON"→";
→John 1:1%1
.END
"in the beginning was the Word all right, but it wasn't a fixed number of bits"
.BEGIN TURN ON"→";
→R. S. Barton, %3Software Engineering%*
.END

Enough philosophy. It will be important to distinguish between LISP
as a descriptive  notation and LISP as an implemented representation.
For historical purposes, we will call the descriptive notation
%2M-LISP%1 and call the implemented version %2S-LISP%1. 
When no confusion is likely, we will dispense with the prefix.

.GROUP;
Since the implemented aspects of the language are most important to us now,
we will begin by looking at the macroscopic structure of a contemporary
machine.  Its basic item of information will be called a %2word%1.
That word will consist of binary bits, zero and one:

.BEGIN SELECT b;NOFILL;PREFACE 0 MILLS;group;
.TURN OFF "%","#","α";
.TURN ON "∞" FOR "%";

		        ⊂ααααααααααα⊃
		        ~ 01 ... 10 ~
		        %ααααααααααα$

.END
.APART
The size of a word is not too relevant for this discussion, however
we will assume that within our machine, each such word is of the 
same number of bits.  
Before dealing with the execution mechanisms of our machine,
we need to discuss a slightly larger unit of information.

In most machines, the words are not simply  scattered about like loose
paper on a desk top. Rather, they are arranged neatly (too neatly!)
like the pages in a book. Each word is assigned  a page number called
a %2location%1.
We will call a sequential collection of computer words a %2vector%1.
For example:
.BEGIN SELECT b;NOFILL;PREFACE 0 MILLS;group;
.TURN OFF "%","#","α";
.TURN ON "∞" FOR "%";

		        ⊂αααααααααα⊃
		  100   ~ 10 ... 1 ~
		        εααααααααααλ
		  101   ~ 01 ... 1 ~
		        εααααααααααλ
			   ...
		        εααααααααααλ 
		  111   ~ 11 ... 0 ~
		        εααααααααααλ
		 1000   ~ 10 ... 1 ~
		        εααααααααααλ
			     ...

.END
The numbers preceeding the words are the locations of the
words. In this example we have sketched the vector from locations
%34%48%1 through %310%48%1#⊗↓With the occurrence of %34%48%1, we have 
introduced another number base; for sake of argument, we will use base
eight, and write %3n%48%1 whenever we wish to make sure that %3n%1
is to be understood as an octal number.←.

Over this simple matrix of words and vectors  the computer industry
 has presented a veritable orgy of
representations for instructions and  data items.
We will not yet restrict ourselves to a particular machine, but will
continue to describe common properties of such machines.
A ubiquitous feature is the execution cycle of a stored program machine.

For simplicity,
we will assume that the architecure is a single-address instruction
machine. This implies that each instruction of our machine will
specify two parts; an operation (something to do), and an operand
(something to do it to or with).  Since many operations we wish to perform
expect a couple of participants, the  single address format must also
reference an implied participant. For our purposes⊗↓This is not
a tutorial on machine architecture; we will discuss such details later.
The point here is to generate some common ground and terminology.
The uninspired machine description may be tedious, but alas is
almost contemporary.← name the unindicted co-conspirator, %2AC%1.
For example, an instruction %3ADD#100%1 would mean form the sum of the
number represented in location 100 and the number represented in 
%2AC%1; place the summation back in %2AC%1⊗↓Thus the result of the
addition is "accumulated" in %2AC%1; %2AC%1 is also called the
"accumulator".←. Thus %2AC%1 acts like a special machine
location; it can contain information.
Or %3JMZ#101%1 might
mean "begin execution at location %3101%1 if the contents
of %2AC%1 is a representation of zero; otherwise execute the
instruction following the %3JMZ%1". This verbiage is getting
excessive. 

First, the word "representation" appears frequently.
That is intentional; we must be clear on the difference between an
object and its representation; that's what abstraction is all about.
Abstraction and representation are
recurring themes in these articles. Next, 
consider our hand-wave at the instructions
in the %3ADD%1 and %3JMZ%1 examples. That discussion was 
intentionally vague; the
actual instruction format is irrelevant. Finally the vagueries in
the execution of these instructions is %2not%1 irrelevant. How a stored
program machine executes its instructions %2is%1 important to our LISP
discussions.

There is another implied "volunteer" in our machine  besides %2AC%1.
This is the %2program counter%1, abbreviated as %2PC%1.  %2PC%1 is used
to control the execution path of a program. If %2PC%1 references
an instruction like the %3ADD%1 above, then the machine executes the addition
and then prepares to execute the next instruction in the sequence. 
The details of the %3JMZ%1
are a bit more complicated. If the contents of the %2AC%1 is  (a representation 
of) zero then the machine will place %3101%1 in the %2PC%1
so that it can execute the instruction in location %3101%1; otherwise
the instruction following the %3JMZ%1 is executed.
Our intent should be clearer now, but we can do better  with a 
diagram. Something like:
.BEGIN TABIT2(27,30);GROUP;TURN OFF "←";

\%al:%3\C(%2IR%3) ← C(C(%2PC%3))
\\C(%2PC%3) ← C(%2PC%3) + 1
\\ %aexecute %3C(%2IR%3)
\\%ago to l
.END

That's quite a mouthful, but it's all notation.
%3C(x)%1 is read "contents of %3x%1"; the arrow "←" is read "replaced by".
The %2IR%*, or %2Instruction register%1, is an internal register 
used to hold the instruction we are to execute. 
So step-by-step the diagram reads: "the contents of %2IR%1 are replaced
by the contents of the contents of %2PC%1"; that gets the next instruction.
Next, "contents of %2PC%1 are replaced by contents of %2PC%1 plus %31%1.
Note that %2PC%*
 is incremented %2before%* execution of the instruction. If we
incremented %2PC%1 %2after%1 the execution
of the instruction, and the instruction were a %3JMZ%1-type
instruction, then the %2PC%1 might get a spurious incrementation.
Finally we execute the instruction and then go back to fetch  
the next instruction. Not very interesting, but embellishments of this
basic cycle will get us to LISP.


Since our machine is not to be too unconventional
(after all it is to be our model for LISP) we will assume that
any such word can contain an instruction or data⊗↓Several machines
enforce a policy of strict separation between instruction and data.
That policy can be enabled either by defining a partition  of memory 
between programs and data, or by requiring a "type code" on each word
with separate codes for data words and instruction words.←. Indeed,
the traditional situation is that the interpretation of a word
depends on the way the execution mechanism of the machine accesses the word.


For example, the contents of a location can be used both as an instruction
and as data; if location %3101%1 contained the representation of the
instruction %3ADD#101%1, then  the execution cycle for that instruction would
involve location %3101%1 in both roles; instruction %2and%1 data.
This dual role of instruction and data occurs in less ad hoc situations.
An assembler converts an external string of characters into a vector of
bit patterns which a loader finally converts into real machine instructions.
Many of the bit patterns which the loader receives from an assembler are
simply machine "instructions", however the loader acts on them as data items;
it does not execute them.


Several machines allow certain  embellishments of the operand field of
an instruction;  indirect addressing is one example. If an operand is
fetched indirectly, that means that contents of the operand field
are not used directly as data, but are interpreted as a further address
and the contents of that further address are examined. If the machine
allows  arbitrarily deep indirect addressing, that further address
is examined to see if it specifies additional indirection.
This chain of indirect addressing must terminate with a "real" address
if the instruction which instigated this mess is ever to complete
its execution.

For example, 
let a modifier %3i%1 indicate indirect addressing;
then %3ADD#10#i%1 means  don't add the contents of location %310%1
to %2AC%1 but look at the contents of location %310%1 to determine
the address. If the contents of location %310%1 is %32%1, then the contents of
location %32%1
will be added to %2AC%1.
If location %310%1 contained %32#i%1, then 
indirect cycle continues and the contents
of location %32%1 would be inspected for an address.
However if the contents of location %310%1 is %310#i%1, then we
will continue to fetch the contents of location %310%1,
looking for an operand which will not be forthcoming. 

Sigh, you say; this is all old hat.  But that's part of the point.
We should 
examine several of the  conventions of this machine, asking
if they are fundamental to the architecture or are more whims or historical
accidents⊗↓After all the original Von#Neumann machines were numerically 
oriented. There is a very interesting paper on the practical design
proposed by Alan Turing (of the theoretical Turing machine fame); 
Turing's machine had a much more non-numerical flavor. See ⊗↑[Car#75]↑.←.
Why should data be numerical? Why should the instructions be sequential?
Why do we need accumulators? Let's be constructive and examine indirect 
addressing more closely.
Indirect addressing is actually a special case of an interesting idea:
instead of requiring that the operand  be a data item, let the
operand specify a further operation. There are several problems
with this scheme, none of which are insurmountable as we shall see.
However, the most important problem for our current concerns
is: if an operand may specify a further operation, then we must
have a way of terminating the "get-new-operand" fetch. We saw two
solutions in the indirect address paradigm:
.BEGIN INDENT 0,2,2;
%21.%1 An instruction will not invoke indirection if the %3i%1 modifier
is not present in the instruction.

%22.%1 An indirect addressing cycle will terminate 
the operand fetch when it comes across
a reference which does %2not%1 contain the %3i%1 modifier.
.END
These two solutions generalize nicely:
.BEGIN INDENT 0,2,2;
%21.%1 Have operations which look no  further. That is, their operand 
may %2look%1 like  an operation, but it is not to be taken as such in the
current context.  
For example⊗↓We have sneaked into our assembly language, UAL (Unspecified
Assembly Language).←:
.BEGIN SELECT b;NOFILL;PREFACE 0 MILLS;group;
.TURN OFF "%","#","α";
.TURN ON "∞" FOR "%";

		        ⊂ααααααααααα⊃
		 loc    ~ ADD   loc ~
		        %ααααααααααα$

.END
When we execute %bloc%1, we also access %bloc%1 as data.

%22.%1 Supply each word with an indicator that distinguishes  data 
from instruction. The operand fetch would terminate when a "real"
operand was fetched.
.END

As we have already  noted, some machines do supply a data-instruction
indicator (though not for the purpose we have ascribed to it);
and as we have further noted, we do %2not%1 plan to follow this policy.
The freedom to 
move freely between data and instruction is  very powerful, albeit
dangerous!
We'd like uniform access to program elements and data elements. That is,
an instruction can reference either data locations or instruction locations.
In terms of our current machine this means:
.BEGIN GROUP;INDENT 5,5,5;
If a location is referenced by the %2PC%1 then its contents is decoded
as an instruction. If a location is referenced as an operand then its
contents is taken as data.
.END

We want similar flexibility in a LISP machine. What "arbitrary" decisions
in the current architecture should we replace with new "arbitrary"
decisions. Well, the data items are particularly puny; what can you do
with numbers, anyway?  As an initial generalization, we might
consider a "vector" machine. Here, the basic data units would be 
vectors of (representations of)  numbers. An interesting
generalization; the %3ADD%1 operation might now specify the 
component-wise addition of two vectors, etc...#. Also programs
would be representable as data items, since they are vectors.

That's some improvement⊗↓It's called APL←. But we're still rather
pedestrian. Data and programs are both represented linearly, and the data items
are all representations of numbers. Surely we can do better.

First, realize that most programs are %2not%1 linear; they typically have
jumps and subroutine calls. A linearity is imposed on program structure
because of the implied addressing of the machine (%2PC%1#←#%2PC%1+1,#thank#you).
Casting  a jaundiced eye at data, we note that much data is non-numerical
in nature; and much of that information has more complex structure than that
supplied by a "vector" machine. 
"Ah, Hah!", you exclaim; we might want vectors, of vectors, of ...#vectors,
 because that's a more general structuring of data and could be used
to reflect the non-linear structure of programs, and#... 

Excellent! Now you're ready for a LISP machine!
.Sec(LISP)
.ss(Introduction)
We will define the "assembly" language for LISP at a 
level of abstraction similar to the handwave of the previous
section. For example, we said "%3ADD#loc%1" was called an instruction in UAL,
without saying anything about how such an "instruction" was
represented in our machine: which part of a word contains the
representation of "%3ADD%1"? who is %3loc%1? and how is it represented in the
machine?
We will continue that level of detachment through several of these articles.
But the moment of truth will come; we %2will%1 reveal the inner mysteries
of a LISP "assembler". In fact we will even describe such an "assembler"
which will produce code for a machine as sedate as a 
contemporary micro-processor. So have patience.

.Ss(LISP data structures)
Our assembly language will be called %2S-LISP%1.
Before introducing the constructs of any language, we must
discuss the constants or data items of that language.
In UAL we could expect to find numeric constants: 1,#43,#etc.; and
we would expect that a UAL assembler would translate those constants
into machine representations. Similarly for LISP. Our 
analogous constants are called %2atoms%1. An atom may be a numeral
or it may be a string of upper case alpha-numeric characters subject to the proviso
that the first character in the string is an alphabetic character.
These non-numeric atoms will be called %2literal atoms%1 or %2identifiers%1.
.BEGIN TABIT2(20,35);GROUP;
For example:\atoms\non atoms
%3\ABC123\2a
\12\a
\A4D6\$$g
\NIL\ABD.
\T\(A , B)
%*
.END;
Atoms can be of arbitrary length; it will be up to our clever
assembler to figure out what to do with them.


Recall your stroke of brilliance: you wanted to represent vectors
of vectors of#...#vectors. We will build your vectors out of atoms and
other vectors. However, being good computer scientists, we %2must%1
insist on some  new terminology. We will call your
vectors %2lists%1 and will build %2our%1 lists as follows:
.BEGIN INDENT 0,0,5;
%21.%1 Any atom or list can be an element of a list.

%22.%1 Given any collection e%41%1,#...#,e%4n%1 of list elements,
then %3(%1#e%41%1,#...#,e%4n%3 )%1 is also a list.
.END
.BEGIN TABIT1(10);GROUP;
So
\%3(A, B)%1    is a list; as is
\%3(A, B, C)%1    ; as is
\%3(A, 1, (ABC, 23)) %1.
.END
Swell. Note that the last example is a list of three elements;
its third element is also a list#--#of two elements: the atom %3ABC%1
and the numeral %323%1.

We will continue to ignore the question of how such lists can be
represented in the machine; that's the assembler's problem.
.ss(LISP operations)
We want to describe primitive operations (or machine instructions, if you
wish) for the LISP machine, and we want programs on that machine
to look like data items. After a moments thought, you should 
expect us to say that a program will be a list. We will go further:
each instruction will also be a list.
The basic form of each instruction will be:
.BEGIN CENTER;SELECT 3;

( %1<operation>%3,%1 <operand>%41%3,%1 ...%3,%1 <operand>%4n%3 )%1 
.END
Notice that we have generalized on the single-address machine; some
operations will expect more than one operand. Before we
enumerate the primitive operations, keep in mind that we
expect to handle cases when an  operand may itself be an operation.
Also remember that the LISP machine will be using assembly language.
For comparison, when we write 
.BEGIN CENTER;SELECT 3;

(x+y)*z
.END
on paper, we would translate it into something horrible like:
.BEGIN TABIT2(15,25);SELECT 3;GROUP;
\LAC X \%1;load the %2AC%1 with a representation of the value for %3x%1.
%3\ADD Y \%1;add the representation of %3y%1
%3\MPY Z \%1;multiply the result by the representation of %3z%1

.END
for our UAL assembler.  The LISP assembler also is an internalized version
of an external notation. However the translation is not so tortured
as that involved with UAL.  In fact, as we see in the next paragraph,
the translation is so simple that LISP cognoscenti frequently dispense
with the external notation and communicate strictly with the internal
notation. The effect is amazing, beautiful, and very powerful.
We have the benefits of a higher level notation and have the flexibility
of machine language, to wit, we can write programs which modify
programs, or more simply we can make programs look like data structure
and data structure act like program. As a higher level
language, LISP machine language (S-LISP) is unique
in that aspect⊗↓The list processing language, IPL-V, ⊗↑[New#61]↑
also had this property; however that language was closer to 
traditional asembly code than to high level languages.←, and we 
will explore the benefits of this uniqueness
quite soon. Let's start.

We have described LISP data structures: atoms and lists. We now need some
operations on those data structures. We introduce instructions to decompose
lists, just as we should have  a %3SUB%1traction operation in UAL to
decompose numbers. One decomposition operation is called %3first%1
and extracts the first element of a list. For example:

.BEGIN CENTERIT;
←%3first[%3(A, B, C)%*] %1gives %3A%1

.END
A lot happened to you on that simple line; think about it.
We  introduced a notation, called %2prefix%1 notation, meaning that
the operation (%3first%1)  preceeded the operand(s)##(%3#(A,#B,#C)%1#).
And we used "[" and "]" to set off the operand from the operation.
For a more familiar example, "%3(x+y)*z%1" would be written
"%3*[+[x;y];z]%1".  A little more notation snuck in: ";" is used to
separate operands.  This prefix-style notation is what we will use
for the LISP formalism (M-LISP). That should raise  questions: how do we
reconcile the formalism of M-LISP with the assembly language of S-LISP?
If we  program in  S-LISP, why worry about M-LISP? The first question will
be answered almost immediately. The second question is more problematic;
its resolution (if such exists) will be postponed; for the moment
we will learn about the programming language LISP and will use
M-LISP in an informal way.

Let's handle the question of M-to-S-LISP translation: how to represent
prefix notation as lists. It's almost straightforwrd:

.BEGIN CENTER;

%2Prefix Notation%1
%1<operation>%3[%1 <operand>%41%3;%1 ...%3;%1 <operand>%4n%3 ]%1 
.END

.BEGIN CENTER;

%2List Notation%1
%3( %1<operation>%3,%1 <operand>%41%3,%1 ...%3,%1 <operand>%4n%3 )%1 
.END

But "almost" isn't  good enough in programming⊗↓Note that 
%3( %1<operand>%41%3,...%1 <operation>%3,%1 ...%3,%1 <operand>%4n%3 )%1 
is also a representation. It is not a good representation since it's
unnecessarily difficult to discover the <operation>-part.←.
Here are the problems:

.BEGIN INDENT 0,2,2;
%21.%1 An "operation" in prefix notation is something like "%3first%1"
or "+", whereas an "operation" in list notation must be an atom
or a list. 
.BEGIN FILL
We can legislate a solution here: %3first%1 translates to
%3FIRST%1, + to %3PLUS%1, and * to %3TIMES%1, etc.
.END

%22.%1 Recall that we want to allow operands to specify further operations.
But we also need some way for stopping the "get-next-operation" fetch;
that is, we need some way of recognizing "real", or constant, operands.
.END

That's easy in M-LISP: %3(A,#B,#C)%1 %2is%1 a constant; it's
tricky in S-LISP: is %3(FIRST,#(A,#B,#C))%1 an S-LISP instruction?
Maybe, maybe not. Compare the situation on a traditional machine:
is a particular bit pattern an instruction? Maybe, maybe not!
It depends on how that bit pattern is referenced. Same with S-LISP;
(question: what M-LISP expression does
%3(FIRST,#(A,#B,#C))%1 represent?). Our quandary is similar to that of
the traditional machine: we must have a way of  telling the execution device
that a particular "bit#pattern" is to be taken as a data item even though
it may look like an instruction.
Our solution is to supply our machine with an operation   which
says "my argument is data; period!" That operation   is named %3QUOTE%1
and is used whenever we encode an M-LISP 
constant --#an atom, or a list#-- into an S-LISP instruction.

Wow! all this from "%3first[(A,#B,#C)] %1gives %3A%1", and we haven't even gotten to
the "gives"  yet! At least we can represent
%3first[(A,#B,#C)]%1 now. It's:
.BEGIN CENTER;SELECT 3;

(FIRST, (QUOTE, (A, B, C)))
.END
It's not too pretty, but at least its better than %3LAC, ADD, MPY,%1#...#!
In fact, the more precise analogy is to require one to program with the
numeric representations of the instructions. That's truly painful to 
behold.


One useful cosmetic  in LISP programming is to drop the commas:
.BEGIN CENTER;SELECT 3;

(FIRST (QUOTE (A B C)))
.END
Before discussing the execution cycle of our machine, let's consolidate
our discussion of S-LISP assembly language.
Our instruction format will be a list consisting of a (representation of)
operation, followed by the 
(representations of  the) operands which the operation is to manipulate.
Those operands may themselves specify operations, but may specify
constant operands by using the %3QUOTE%1 operation. For example:
.BEGIN CENTER;SELECT 3;

(FIRST (FIRST (QUOTE ((A B) C))))%1 specifies:
.END
.BEGIN CENTER;SELECT 3;

first[first[((A B) C)]]%1 and would have value %3A%1; right? 
.END
How are values obtained on a LISP machine? A future article will be
entirely devoted to the architecture of a LISP machine. For the current
discussion, the LISP machine is a calculator. We type in an S-LISP
expression, and the calculator displays the result.  The evaluation of the
input expression can be quite involved. If an operand specifies a further
operation, then the current instruction is suspended while that subsidiary
computation is performed.

.BEGIN nofill;

So, evaluating    %3(FIRST (FIRST (QUOTE ((A B) C))))%1     would involve the following:
.END
The leftmost %3FIRST%1 must wait since its operand requires evaluation;
similarly the next %3FIRST%1 must wait to take care of 
its argument. But its argument is a %3QUOTE%1-ed expression.
#%3QUOTE%1 is kind and returns the list %3((A#B)#C)%1. The inner 
%3FIRST%1 completes now, returning %3(A#B)%1 to the outermost
%3FIRST%1; it is nudged into activity and finally returns %3A%1.

LISP is a %2very%1
interactive language; probably the %2most%1 interactive language we have!
LISP's interactive nature is much appreciated when trying to program
complex ideas. As a simple case, consider:

.BEGIN SELECT 3;CENTER;
(FIRST (QUOTE (FIRST (QUOTE (A B))))
.END
This example illustrates the duality of program and data stucture in LISP.
The  embedded expression %3(FIRST#(QUOTE#(A#B))%1 has the appearance of a 
LISP instruction, and in other circumstances, it %2could be%1 an instruction.
However, that expression is surrounded by %3(QUOTE#...#)%1 in the current example;
Therefore it is simply a list; i.e., a constant. The final result of the
computation will be the atom %3FIRST%1, since the LISP instruction
is encoding the expression:
.BEGIN SELECT 3;CENTER;

first[(FIRST (QUOTE (A B)))]
.END


If we had to punch cards  or paper tape, compile the program and then
attempt to decode the output, our understanding of LISP would come much
more painfully. So a LISP machine is a sophisticated calculator.
Clearly we won't have a very impressive calculator unless we 
have more instructions than %3FIRST%1. 



We also have an instruction named %3REST%1⊗↓When we say "instruction"
we mean a S-LISP expression. You may either think of the
instruction as a machine operation or as the translation of
an M-LISP expression.← which, like %3FIRST%1, expects a list, as its
argument. The distinction is that %3REST%1 returns a truncated list
with the first element removed.

.BEGIN CENTERIT;group;

←%3(REST (QUOTE (A B C))) %1yields %3(B C)
←%3(REST (QUOTE (B C))) %1yields %3(C).
.apart;
.group;

%1What about:←%3(REST (QUOTE (C))) %1? 
.BEGIN FILL
Common sense should say that when we remove the last element from a list
we get the empty list. LISP is very good about being consistent; the
empty list is correct, and its notation is "%3(#)%1".
.END

Thus ←%3(REST (QUOTE (C))) %1 yields %3( ).

.END
Besides decomposing lists, we should expect to build new  ones.
The operation %3LIST%1 performs that service.
Here are some examples:

.BEGIN INDENT 0,5,5;
%21.%1 %3(LIST (QUOTE A) (QUOTE B) (QUOTE C))%1 yields %3(A B C)%1.
Note that each operand to %3LIST%1 was %3QUOTE%1-ed;
%3(LIST A  B C)%1 means something entirely different. No, we haven't
said what it means yet.


.group;
%22.%1 %3(LIST 2 (QUOTE B))%1 yields %3(2 B)%1. Two things here:
first, we didn't "%3QUOTE%1" the %32%1; it wouldn't be wrong, but we'll
give our LISP machine credit for deciding that numbers are constants.
Second, the %3LIST%1 operation will take an arbitrary number of operands;
three in our first example, two in this one, and none in the next.

%23.%1 %3(LIST )%1 yields %3( )%1.
.END
As with the other instructions (except %3QUOTE%1), %3LIST%1  can
handle instructions as operands.

Try:   %3(LIST (FIRST (QUOTE (A))) (REST (QUOTE (A B))) (QUOTE C))%1.

Dilligence may have been rewarded and you  may have responded:
"%3(A#(B)#C)%1". There's an equal probability that you got mired in 
parenthesis-counting and responded "(?!$≡)". One aid is to resort to
M-LISP and  recast the expression as:
.BEGIN CENTER;SELECT 3;

 %3list[first[(A)];rest[(A B)];C]%1
.END
However, we are attempting to develop our S-LISP expertise, so we should
find some way to make S-LISP expressions more readable. One method is called
%2pretty-printing%1. LISP is a "free format" language;  we are not
restricted to 80-column card images. Pretty-printing exploits this freedom
by using additional lines and spaces to  highlight the grouping in a
complex expression. For example:

.BEGIN CENTER SELECT 3;TABIT2(15,21);

\(LIST\(FIRST (QUOTE (A))) 
\\(REST (QUOTE (A B))) 
\\(QUOTE C))%1
.END

As we get to more complex LISP expressions, we will depend more heavily on
pretty-printing to maintain readability.

Another painful aspect of S-LISP notation can be soothed. Notice that
whenever we represent a constant %7a%1 we write %3(QUOTE#%7a%3)%1; that
gets to be a bore. We therefore introduce an abbreviation, writing
.BEGIN CENTER;

%3(QUOTE#%7a%3)%1 as %9'%7a%1
.END
So the previous example could be expressed as:
.BEGIN CENTER SELECT 3;TABIT2(15,21);

\(LIST\(FIRST  %9'%3(A)) 
\\(REST  %9'%3(A B)) 
\\%9'%3C)%1
.END

Before continuing to more exotic kinds of operations, we need to discuss
another S-LISP operation for building lists; it is called %3CONCAT%1.
##%3CONCAT%1 is a two-address instruction; its first operand can either
be an atom or a list, but its second operand %2must%1  reference a list.
For example 
.BEGIN CENTER SELECT 3;

%3(CONCAT##%9'%3A##%9'%3(B))%1. Note that this represents %3concat[A;(B)]%1.
.END
The effect of executing such a %3CONCAT%1 is to build a new list
whose first element is the first argument of the %3CONCAT%1 and  remainder
of the new list is the second operand  of %3CONCAT%1.
So the example  would evaluate to %3(A#B)%1. Note that %3LIST%1 and %3CONCAT%1
are %2not%1 the same operation. %3LIST%1 takes an arbitrary number of arguments
and builds a list whose elements are those arguments.
On the other hand, %3CONCAT%1 takes an element and a  list,  and adds the
element to the front of the list.
.BEGIN CENTER SELECT 3;

(LIST##%9'%3(A)##%9'%3(C)) %1gives%3 ((A) (C))%1
%3(CONCAT##%9'%3(A)##%9'%3(C)) %1gives%3 ((A) C)%1
.END

So we can decompose lists and make new ones; not a very impressive array
of operations. Notice that all our programs are "straight-line" code;
that is, there are no branches⊗↓%1Indeed, our programs are "one-liners"
in the best APL-sense.←. 
Before introducing %2that%1 complexity there is a bit more we can do with such
nice straight-line programs.
.SS(Definitions and variables)
The interactive nature of a LISP  calculator is greatly enhanced by its 
ability to increase its repertoire of instructions.
For example, if we wanted to define a new operation called %3second%1
which got the second element of a list:

.BEGIN SELECT 3;CENTER;

second[(A B C)]%1 should give %3B%1,
.END
we might write in informal M-LISP:
.BEGIN SELECT 3;CENTER;
second[x] <= first[rest[x]].
.END
We could introduce this new instruction to a LISP machine by:
.BEGIN SELECT 3;CENTER;
(DEFINE SECOND (X) (FIRST (REST X))).
.END

First notice the structure of the definition of %3second%1 (or %3SECOND%1).
We could read it as "define a function named %3second%1 which expects
one operand;  we will name that operand, %3x%1. Then 
the effect of %3second%1 is to perform
%3first%1-of-the-%3rest%1 of %3x%1. One new feature is the occurrence
of %3x%1 (or %3X%1 in the representation). Up to this point we have
dealt solely with operations on constants. Now we're introducing
variables; that is %3x%1  is a variable and %3X%1 is its representation.
As long as LISP can find a value associated with a variable, a computation 
can proceed as if we had used constants. 

Once the definition  has been processed by the machine we
can use that new operation  as if it were part of the original calculator:

.BEGIN CENTER;SELECT 3;
(SECOND##%9'%3(A B C)))
.END
The execution of this expression would proceed  just as before, only now
the machine must reconcile the form of the input expression with the form of the
definition, in essence reducing %3(SECOND##%9'%3(A#B#C))%1 to
%3(FIRST#(REST##%9'%3(A#B#C)))%1. 
Thus %3(SECOND##%9'%3(A#B#C))%1
does what is expected, since the LISP machine  associates the list
%3(A#B#C)%1 with %3X%1 --#the representation of the variable %3x%1.


The  description of
LISP's reduction techniques are some of the most beautiful results in
computer science; we shall spend a whole article on these ideas.
For the moment we shall intuit our way through the examples.

This definitional facility gives us  a nice abbreviational tool.
Yet our programs are still quite simple.
What we need is a means of controlling the flow of
execution --#jumps and tests.

.SS(Predicates)
In traditional assembly language programming we find 
instructions which test for  zero or compare two numbers;
that is  understandable since our data objects are numeric and our operations
decompose and construct numeric representations. In LISP we manipulate
atoms and lists so we should expect operations to test atoms and lists.
Again, LISP does not disappoint us. We have three such "test" operations
in LISP⊗↓Actually, we have more than three since
we can use the definitional facility to add more.←. The test operations are called %2predicates%1.

.BEGIN INDENT 0,6,5;
%21.%1 %3EQ%1: Compare two atoms. That is, %3EQ%1 is a two-address
instruction, and %3EQ%1 will determine if
those two operands represent the same atom.

%22.%1 %3ATOM%1: This single-address instruction tests its operand for
"atom-ness".

.INDENT 0,9,5;
%23.%1 %3NULL%1: This  single-address instuction tells whether or not its
operand represents the empty list, %3(#)%1.
.END

All the LISP operations we have previously introduced (%3FIRST, REST, QUOTE,
LIST,%1 and %3CONCAT%1) have been defined to compute a value. We want to
continue that tradition; therefore our predicates must also produce values.
In mathematics, predicates produce what are called %2truth-values%1 --#true,
or false#--; in M-LISP, we could represent true and false as %et%1 and
%ef%1, say. However, in S-LISP, these truth values must be represented as
data items; 
and so we pick the atoms %3T%1 and %3NIL%1 as their representations.


.BEGIN GROUP;TABIT2(10,40)
For example:

\%2S-LISP\M-LISP%3
\(ATOM##%9'%3A) %1gives %3T%3\atom[A] %1gives %et%3
\(ATOM##%9'%3(A)) %1gives %3NIL%3\atom[(A)] %1gives %ef%3
\(EQ##%9'%3A##%9'%3B) %1gives %3NIL%3\eq[A;B] %1gives %ef%3
\(NULL##%9'%3(A B)) %1gives %3NIL%3\null[(A B)] %1gives %ef%3
.END

.GROUP;
Since the predicates are value-producing they can be used with the other
list-manipulating operations:
.BEGIN SELECT 3;TABIT2(10,20);group;

\(CONCAT\(ATOM##%9'%3A)
\\(LIST 1##%9'%3A)) %1gives %3(T 1 A)%1.
.END
.APART

The results of these predicates have to be listened to if 
we expect to create more than our straight-line LISP programs. This introduces a 
different kind of LISP construct: the %2conditional expression%1.
.ss(Conditional expressions)
The usual jump and skip operations in a conventional machine are
necessary to relate non-linear programs to the linear memory organization.
In some higher level  languages we see "label-and-go-to" 
constructs; to a large extent
these are carry-overs from the machine architecture  and reflections of the
early days of card-oriented computation. The LISP machine is %2not%1 linear
and the language is %2not%1 card-oriented. Therefore we should be able to do
a better job of expressing ourselves.

The basic control unit in LISP is called the %2conditional expression%1.
In M-LISP it is written:
.BEGIN CENTER;

%3[%1p → q;r%3]%1 ##or ##%3if[%1p; q; r%3]%1. 
.END
These notations can be read " If p (is true), then q, otherwise (or else) r."

.GROUP;
The   representation in S-LISP is:
.BEGIN CENTER;

%3(IF %1<representation of p>  %1<representation of q>  %1<representation of r>%3)%1
.END
.APART;

.BEGIN INDENT 0,2,2;GROUP;
The %2meaning%1 of such a conditional expression is as follows:

%21.%1 The instruction represented by p must be a predicate; we evaluate
that expression. If the value is %3T%1 then we evaluate the instruction
represented by q; if the value of p is %3NIL%1 (the representation of
false) then we evaluate r.

%22.%1 The conditional expression must
have a value since every LISP instruction must have some value. 
Its value is either the value of q or the value of r, depending on the value
of p.

%23.%1 The evaluation of a conditional expression is different from the
technique we have used in previous LISP instructions. Previously we have
insisted that we evaluate all of the operands in an instruction. In the conditional
expression, we evaluate the p-operand and,
depending on that result, evaluate either the q-operand or the r-operand; but
we never evaluate both.
.END

.GROUP;
For example:
.BEGIN CENTER ;GROUP;SELECT 3;
(IF (ATOM##%9'%3A)##%9'%3FOO  1) %1gives value %3FOO%1 since %3(ATOM##%9'%3A)%1 gives %3T%1
%3(IF (ATOM##%9'%3(A))##%9'%3FOO  1) %1gives value %31%1 since %3(ATOM##%9'%3(A))%1 gives %3NIL%1


%1Here's a more interesting example:
%3(IF (EQ##%9'%3A##%9'%3B)##%9'%3FOO  (REST (REST##%9'%3(A))))

.END
.APART;

We evaluate
%3(EQ##%9'%3A##%9'%3B)%1 getting %3NIL%1; therefore we look at the "otherwise"
condition. 
That gives us %3(REST#(REST##%9'%3(A)))%1 to evaluate.
The inner %3REST%1 returns %3(#)%1, and now we're in trouble. What should
%3REST%1 do with an empty list?  Any self-respecting programming language
should at least give an error message. A good LISP will do even more as we will see
in a future article⊗↓To whet your appetite, a good LISP can often
display an error message, suspend the current computation,  and then
allow the programmer to modify the program (recall that the program is 
also a data item),  and then continue the computation with the modified program.←.
However our current problem is more  pedestrian. We have glossed over
error conditions and error messages. That slovenliness must be rectified.


Look back at our LISP operations. Which of them can  cause trouble?
%3FIRST%1 and %3REST%1 must be  careful. Those operations should only 
operate on lists, and in fact, on non-empty lists. %3LIST%1 and %3ATOM%1 will
operate on anything, however %3CONCAT%1 and %3EQ%1  are more  particular.
The first operand to %3CONCAT%1 is arbitrary, but its second must be a list;
and %3EQ%1 expects both of its arguments to be atomic, otherwise it should
complain.

Perhaps now you will see why the conditional expression does not 
evaluate all of its operands. Frequently one of the expressions in the
conditional would give an error message if it were evaluated, but the
thrust of the computation we wish to perform is carried in the other
branch of the conditional. It would be %2most%1 frustrating to watch our
computation terminate with a message  because the %3IF%1 wanted to
evaluate %2both%1 operands.


We have introduced all the instruments on the LISP orchestra. Now it's
time to make some music.

.ss(Extended examples)
We will develop three examples of LISP definitions in this
section. That will not be the end of our programming sampler, however.
In the next article we will give a more intensive exposure to
LISP applications, but you should have some time to digest this new
material and let your stomach settle.

.GROUP;
The first example is the most venerable of LISP programs: 
an algorithm to compute the factorial function.
We could  write it as:
.BEGIN GROUP;TABIT2(10,15)

\\%31%1 if %3n%1 is %30%1
\%3n!%1 =
\\%3n*(n-1)!%1 if %3n%1 %a> %30%1

.END
.APART;

As you are probably beginning to notice, we try to sneak  little "lumps" of 
information in, and hope that you don't choke. So too with the last paragraph.
First, the "definition" of factorial is a new notation, but you probably can
decode its intent. But what kind of a definition is it? It's not a program; it
doesn't explicitly give a rule of computation, though you can develop one from the
supplied information. The key lies further up the page in the two words
"function" and "algorithm". 

.BEGIN TURN OFF "{,}";TURN ON "#","←";
Mathematically a function is a
mapping such that for any given argument in the domain of the function there
exists a unique corresponding value. 
Typically, a definition of function %3f%* involves saying that %3f%*
is a set of ordered pairs %3f#=#{#<x%41%*,#y%41%*>,#...}%1; the %3x%4i%1's are
all distinct and the value of the function %3f%* for an argument %3x%4i%1 is
defined to be the corresponding %3y%4i%1.
No rule of computation is given to 
locate values; with the first definition it is implicit that the internal structure
of the mapping doesn't matter; in the set-theoretic definition, the correspondence
is explicitly given.

An algorithm  is a recipe or procedure for
computing values for a function. The factorial function, %3n!%*,
is the  set of ordered pairs,

←%3{<0,1>, <1,1>, <2,2>, <3,6>, ...<n,n!>,  ...}%1.
.END
The factorial function can be computed by
many different algorithms, as we shall see. 

That's really swell, but what does it have to do with programming on a 
%7m%1-computer?  Answer: it's another manifestation of our 
object-representation idea;
an algorithm is a particular representation of a function. 
The more "representation independent" an algorithm becomes, the more
"function-like" it becomes.
High level languages tend to abstract from the data structures away from 
"bits-and-bytes";
%2very%1 high level languages seek to eliminate 
unnecessary order dependence in carrying out a computation.
This notion
will be important to us since we will be looking for algorithms which
express our essential ideas %2but no more%1. 
 We want to be able to thread a delicate line between
too much machine-dependence and too much abstraction. Either extreme will
cloud, rather than clarify.


This discussion is getting  too
far-afield, but the distinction between function and algorithm %2is%1 important.
It's like knowing that there %2is%1 a path through a maze and knowing %2a%1 path
through a maze. We practical-minded rats  want 
a bite of the computer science cheese. Once our baser appetites have been
satisfied, the more abstract concepts are more digestable.
Back to our patient factorial function.

We want to convert the description of  the 
factorial function into a complete LISP algorithm.
The "if"-structure can be converted into a  conditional expression,
and we can name the new operation %3fact%1. We need a multiplication
operation; we can  assume our LISP machine has  such an operation⊗↓Not
a rash assumption, indeed. You might like to give a LISP definition of
multiplication, given the existence of a successor function, %3add1[x]#=x+1%1.
While we're on the subject of LISP arithmetic, we should put a few myths
to rest. LISP processors  do not have to be inefficient arithmetically.
In a test at the MACSYMA project ⊗↑[Fat#73]↑, the LISP compiler
produced better code than the resident FORTRAN compiler. Also
several LISP's have "arbitrary precision" numbers: "what's the factorial
of %31222%1, please?"←. We may also assume the existence of a 
simple subtraction function, %3sub1[x]#=#x-1%1⊗↓Again, you might
write the more general subtraction operation, %3diff[x;y]%1.←.

.GROUP;
So here's LISP's first factorial algorithm in M-LISP:
.BEGIN SELECT 3;center;

fact[x] <= [eq[x;0] →1; times[x;sub1[x]]]
.end
.APART;

.GROUP;
A simple translation to S-LISP and it will fly:
.BEGIN GROUP;SELECT 3;TABIT2(10,32);

\(DEFINE FACT (X) (IF\(EQ X 0) 
\\1
\\(TIMES X (FACT (SUB1 X)))))
.END
.APART;

Can't get much more straightforward than that with out resorting to
crypticism. Readibility of programs is no small matter.

The major mystery encouraged by LISP is its use of %2recursion%1.
There are several interpretations of the term, but for our current purposes
it will mean that a program is able to invoke itself either directly
or indirectly through a chain of "recursions": A calls B, which calls C, 
 ...,#which calls A.##  %3FACT%1 exemplifies direct recursion since an application
of %3FACT%1 occurs within the definition of %3FACT%1. 


A typical recursive definition  has several characteristics:
.BEGIN INDENT 0,2,2;
%21.%1 It had better involve a conditional expression, or we're in big
trouble. A definition like %3foo[x]#<=#baz[foo[bar[x]]]%1 will cause nothing
but grief. The conditional expression will contain two basic
parts: the %2termination case%1 and the %2general case(s)%1.

%22.%1 The termination case describes what to do when a primitive data structure
is recognized. In mathematics, and therefore in the %3FACT%1 example, we
tend to consider the integers built from zero, using the successor 
function, %3add1%1. Therefore, our termination case in %3FACT%1 involves
recognition of %30%1, and terminates with value %31%1.

%23.%1 The general cases involve "composite" data structures. Again, in mathematics
we assume that the positive integers are built up from zero. Therefore we can
decompose a positive (composite) integer by subtracting one. 
The essential idea is that reducing the complexity of the argument
in a recursive  call will thereby reduce the complexity of the problem.
That's an old trick; what recursion says is that we can solve the
original problem by reducing it to a simpler case of the %2same%1 
problem. If we persist, the problem will solve itself before we get tired
of  reducing; it's like dieting.

.END
If a recursive definition sounds similar to a description of mathematical
induction, your right. The techniques involved in finding the right
inductive steps are similar to those involved in finding the right
break-down for a recursive definition.
The use of recursive definitions
is an incredibly powerful technique; in a later article we will display the 
mechanisms which support recursive evaluation. For the moment we will settle
for a quick sketch of the evaluation process.

Assume we wish to evaluate %3(FACT#2)%1. Our calculator will locate the
definition of %3FACT%1 and associate %32%1 with %3X%1⊗↓%1If "locate" and
"associate" bother you, have patience; we will give precise descriptions of
these terms in future articles.←. The calculator is faced with the conditional
expression, and determines that %3(EQ#X#0)%1 has value %3NIL%1.
Therefore we must evaluate %3(TIMES#X#(FACT#(SUB1#X)))%1.
We can evaluate %3X%1; it's %32%1. However, we must suspend our
activity while we compute the second operand to %3TIMES%1. That computation
involves a further suspension, since we must compute 
%3(SUB1#X)%1, the operand to %3FACT%1. Yes, %3FACT%1 is the
name of the algorithm which got us into this mess, but our
calculator neither knows nor cares.## %3(SUB1#X)%1  yields %31%1 and we
can apply the operator named %3FACT%1 to that value. 

Our clever calculator
associates %31%1 with %3X%1 and, with a feeling
of %3deja#vu%1, begins to evaluate the conditional expression
which makes up the body of %3FACT%1. It discovers that %31%1 is still not
%3EQ%1 to %30%1, and evaluates  %3(TIMES#X#...)%1 again, this time
with %3X%1 giving value %31%1. ##%3SUB1%1 gives %30%1 and we evaluate
%3(FACT#0)%1. At last, sigh, the expression %3(EQ#X#0)%1 yields %3T%1,
so we return a value %31%1 to the last suspended %3(TIMES#...)%1.
In that context, %3X%1 had value %31%1 so we (essentially) evaluate %3(TIMES#1#1)%1.
That operation completes, returning %31%1 to the previously suspended
 operation, which was the outer %3TIMES%1; in that 
context %3X%1  has value %32%1 and therefore
we finally return the value of %3(TIMES#2#1)%1; it's %32%1.

The calculator expects a lot; it must save and restore several
values associated with %3X%1. For the moment, trust it; we will soon bolster
that trust with some real facts about implementation.  The important
point now is to understand how to %2use%1 the tool.

.GROUP;
Next, a real-life LISP example. Assume that we want to test the equality of
two lists, where equality means that each element of  two lists is identical
and the order in which those elements occur is identical. The identity relation
also extends to sub-elements of lists. For example:

.BEGIN GROUP;TABIT2(20,45)

\%2equal\ non-equal%1
\%3(A B C)   (A B C)\(A B C)  (A B D)
\%3(A (B C) D)   (A (B C) D)\(A (B C) D)  (A (B D) D)
\%3( )  ( )\(A (B (C) D))  (A B C D)
.END
.APART;
An algorithm to compute this extended equality, --#call it %3equal%1#--,
should  be recursive.  In the %3fact%1 example we recurred on the size of the
number, reducing it at each step. Assuming that the original 
number was non-negative, we knew that the reduction process had to 
arrive at zero sometime.
Recursive processes share this phenomenon. Regardless of the kind
of object we  are dealing with, all we need to do is find the
right way to decompose an object, and then pounce on the pieces.
The decomposition operators we have for lists are %3first%1 and %3rest%1.
We also have to know how to stop the decomposition. In %3fact%1 we tested
for the occurrence of zero; in lists we can test for the occurrence of
an empty list, and since we are assuming that  elements of a list may either
be sublists or atoms, we need to test for the occurrence of an atom.
Cleverly, we have included such testing mechanisms: %3null%1 and %3atom%1.
Let's try  the simplest possible case first: the empty list.

.BEGIN SELECT 3;GROUP;NOFILL

(DEFINE EQUAL (X Y) (IF  (NULL X) ...? )
.END
Well, we've stuck you with S-LISP, but you should survive.
What should we do? If %3x%1 is empty, then we will only have equality
if %3y%1 is also empty; otherwise we will have an inequality.
Watch my hands closely:
.BEGIN SELECT 3;GROUP;TABIT2(27,31);

(DEFINE EQUAL (X Y) (IF\(NULL X)
\(IF\(NULL Y) 
\\T
\\NIL)
\...?)
.END

What happened? A lot. Note that we embedded a conditional expression
within a conditional expression. That's fair since  every expression in LISP
has a value. Note also that the interior conditional returns either
%3T%1 or %3NIL%1; but that's what we wanted since %3EQUAL%1 is to encode
a %2predicate%1 and %3T%1 and %3NIL%1 are our representations of the
truth values %et%1 and %ef%1.
Note too that we depend on the order dependence of the conditional evaluation;
we won't test the %3(NULL#Y)%1 expression unless %3(NULL#X)%1 is true.
We won't get to the "%3#...?%1" condition unless %3(NULL#X)%1 is false.

.GROUP;
What happens if the lists are not empty?  Not so fast! We can still have
%3x%1 non-empty and %3y%1 empty; let's take care of that:

.BEGIN SELECT 3;GROUP;TABIT2(27,31);

(DEFINE EQUAL (X Y) (IF\(NULL  X)
\(IF\(NULL  Y) 
\\T
\\NIL)
\(IF\(NULL  Y)
\\NIL
\\...?)
.END
.APART;

%2Now%1 the "%3...?%1" has been reduced to the case that %2both%1
lists are non-empty, and we can massage the pieces with %3FIRST%1
and %3REST%1.  We look at the %3first%1 pieces; if they're equal, then
our decision on the equality of the original lists depends on the
equality of the remainders (or %3rest%1s) of the  lists. If the
%3first%1s are %2not%1 equal, then we can stop immediately with a 
false indication.  This analysis yields two cases: 1)#if the first
elements are atomic, then use %3EQ%1 to check their equality; 2)#otherwise
use %3EQUAL%1 itself on the first elements. Here we go:


.BEGIN SELECT 3;GROUP;TABS 18,22,26,30,34,38,42;TURN ON "\";NOFILL;

(DEFINE EQUAL\(X Y) 
\(IF\(NULL X)
\\(IF\(NULL Y) 
\\\T
\\\NIL)
\\(IF\(NULL Y)
\\\NIL
\\\(IF\(ATOM (FIRST X))
\\\\(IF\(ATOM (FIRST Y))
\\\\\(IF\(EQ (FIRST X) (FIRST Y))
\\\\\\(EQUAL (REST X) (REST Y))
\\\\\\NIL)
\\\\\NIL)
\\\\(IF\(ATOM (FIRST Y))
\\\\\NIL
\\\\\(IF\(EQUAL (FIRST X) (FIRST Y))
\\\\\\(EQUAL (REST X) (REST Y))
\\\\\\NIL))))))
.END

So far our examples have either been numerical or have been predicates.
Predicates only require traversing existing lists; certainly  we will
want to write algorithms which build new lists.  Consider the problem
of writing a LISP algorithm to  reverse a list %3x%*. There is a simple informal
computation: take elements from the front of %3x%*  and put them
onto the front of a new list %3y%*. Initially, %3y%* should be  %3(#)%* and
the process should terminate when %3x%* is empty. 
.GROUP;
For example, reversal of the list %3(A B C D)%1 would produce the sequence:

.BEGIN SELECT 3; TABIT2(32,49);

\x\y
\(A B C D)\( )
\(B C D)\(A)
\(C D)\(B A)
\(D)\(C B A)
\( )\(D C B A)
.END
.APART

What follows is  %3reverse%*, where we use a sub-function
%3rev%9'%1 to do the hard work and perform the initialization with 
the second argument to %3rev%9'%1.

.BEGIN CENTERIT;SELECT 3;GROUP;
.P97:

←reverse[x] <= rev%9'%*[x;( )]

←rev%9'%*[x;y] <= [null[x] → y;  rev%9'%*[rest[x];concat[first[x];y]]]
.APART
.END

This %3reverse%* function builds up the new list 
by  %3concat%*-ing
the elements onto the second argument of %3rev%9'%*%1. Since %3y%* was initialized
to %3(#)%* we are assured that the resulting construct will be a list.

We leave it to the reader to translate this algorithm into S-LISP.

.GROUP;
As a final example, here's another algorithm for the factorial function.

.BEGIN TABIT1(10);SELECT 3;GROUP;CENTERIT;

←fact%41%*[n] <= fact%9'%*[n;1];

←fact%9'%*[n;m] <= [eq[n;0] → m;  fact%9'%*[sub1[n];times[n;m]]]
.END
.APART;
.SS(Summary and preview)
A lot has happened explicitly and a lot more is lurking just under the surface.
This is a good place to stop and take note.
Much of what we have discussed is  more general than just LISP;
we have introduced several important facets of  programming languages.

We have discussed data structures (atoms and lists). This discussion
included the actual definitions of the items; those definitions
were of two kinds: explicit definitions of the primitive data items
(atoms) and recipes for constructing composite data items (lists).
We  then introduced operations on those data items. Those operations
involve three basic kinds of manipulation:

.BEGIN INDENT 0,2,2;
%21.%1 We could recognize
different kinds of data structures (%3atom%1 and %3null%1).
These operations are called %2recognizers%1.

%22.%1 We were able to construct composite data structures (%3concat%1 and %3list%1).
These operations are called %2constructors%1.

%23.%1 We could decompose composite objects (%3first%1 and %3rest%1).
These operations are called %2selectors%1.
.END

Any language %2must%1 have such basic selectors, constructors, and recognizers 
to operate on its data structures.
A language must also be able to introduce 
new terminology through abbreviations or definitions.
LISP has such a facility, allowing the introduction of new operators.
An important class of such operators are the predicates; those LISP
functions which give either %et%1 or %ef%1 as value (or return %3T%1 or
%3NIL%1 as value in the S-language). Predicates can be more general
than simple recognizers, since we have %3eq%1, a version of  the
equality relation.


Another important aspect of programming languages is their ability to
specify alternative paths in a computation and specify the
order in which  computations are to be performed. These basic facilities
are called %2control structures%1.  LISP's control structures are
conditional expressions, recursion, and operand evaluation.
The first two are reasonably obvious ways of diverting a computation
from its straight-line path. Operand evaluation may not be so apparent.
The basic idea is that LISP specifies an order in which operands
are to be evaluated. So, when we  write a sequence of operands we must be 
aware of that convention. Specifically, a LISP  calculator will evaluate
the operands from left-to-right. That's not so important itself; what %2is%1
important is that %2every%1 programming language has such little tidbits of
information and programmer's %2must%1 be aware of them. Most languages
resort to voluminous documents, or just 
cloak themselves in obfuscation. The specification of the inner
mysteries of LISP is beautiful simplicity: it is a LISP program named %3eval%1.
These kinds of LISP ideas are as important as those involved in LISP
applications. Before we're finished you will see both.

We close with a preview of coming events.

In the  next article we examine some more detailed LISP applications.
In that context we will write several LISP programs. 
We will show that proper LISP programming is as well-structured and modular
as you want to make it. The key idea here is "abstraction".
Our examples will include LISP programs from symbolic mathematics,
game-playing  and tree search, and operating systems and language design.
We will also  talk about the programming
environment which LISP "hackers" have come to expect; and will
show why  LISP is so well-suited to such programming environments.
Specifically, the program-data duality makes LISP editors and debuggers
quite powerful.

In article three we  introduce you to some of the most elegant (but very
practical) results in computer science: the description of LISP's evaluation
process. The description will be given in LISP; what else. 
The process we describe is an elegant introduction to interpreter
construction. Once that
high level description of LISP is understood we are ready for its implementation.
That's the topic of article number four.

How do we reconcile the non-linear program and data structure of LISP with
the linear memory structure of our typical machine? That's the first order
of business in article four. From that, we discuss the business of storage
allocation and management: free lists and garbage collection. We proceed to
a discussion of input and output for LISP; that introduces hashing, parsers,
scanners and more details of the representations for LISP atoms.
For our next trick we
discuss what is needed to make
recursion work on a traditional processor, and what is required to implement
conditional expressions. These, after all, are the main tools of LISP.
This discussion will introduce LISP compilers, since the instructions
which the %7m%1-computer executes to evaluate a LISP expression
are almost the code which a compiler would produce. What 
language will we write our
compiler in? Why LISP naturally.
These discussions of implementing LISP data structures and their
evaluators will require two articles, but in that discussion you will
see a practical implementation of LISP for a %7m%1-computer.
We wait until articles %24%1 and %25%1 to discuss implementations for two
reasons. First, it's is most important that you understand what you're building.
This is not a course in basic carpentry; %7m%1-computers are very fine devices
and their software design deserves to be as elegant. Second, we're lazy; by
article %24%1 we will have discussed most all of the implementation
details %2of%1 LISP %2in%1 LISP. As we intimated above, we write LISP
compilers in LISP; we can also write much of the LISP operating
system in LISP as well.  The technique is called %2bootstrapping%1; its
use saves us an incredible amount of time energy and hot air.
While we're on 
the subject of hot air, we will also discuss editors and debuggers in more detail
these sections.

The final article will discuss some of the practical and theoretical
implications of LISP. 
We will talk about the ideas of proving programs correct and show how the
simple structure of LISP makes such endeavors believable.
We will talk about an advanced LISP topic called functional variables, and
show its application to operating systems design  and interactive programming
systems.
We will examine some of the AI languages; all of these languageas are LISP dialects.
We will summarize some of the  implications of LISP: where is it going? why 
has it been so long-lived? why is it the dominant language in AI?
why should LISP be attractive to the %7m%1-computer community?
LISP sits right in the crossroads
for those interested in computer science. 
By the time we're finished you will know all there is to know.

Can LISP run on a micro-computer? Sure; it's been implemented on an
F-8 and even on a HP9825 calculator⊗↓I'd be interested in hearing about any
other implementations.←. The problems are not (initially) those of size, but
are problems of sophistication.  A good system on a small machine
should only get better on a large machine. 
Our implementation requires
care and cleverness, but that's what this is all about anyway. Isn't it?
.BEGIN VERBATIM
      VI(new II)
applications  and simple debugging and editing
data base a la planner etc

differentiation
simplification
parsing:sdio,pratt recursive descent,petrick
eval of poly

tree search

operating system

debugging and editing in fact example;subst[x;y;z]


introduce abstraction
.END

.SEC(Applications)
Hopefully you have had sufficient time to reflect on the 
first batch of material and are ready for the second sermon.
In this episode we will explore several reasonably detailed examples.
There are several reasons for this. The most obvious is that LISP %2is%1
a viable programming tool and we should show how to construct LISP
programs which do more than fiddle with abstract ideas like lists.
It's the representation problem again --#how to relate abstract ideas
with concrete reality#--. There are no "seven steps to programming perfection"
in LISP; anyone who thinks programming is easy is brain damaged.
However, we %2can%1 give insights into programming styles which
can control the complexity of  the programming problem⊗↓What %2did%1 he say?!?←.
The tricks lie in following a fine line between  the abstract and 
the concrete. If the algorithm/data structure is over-specified (too concrete)
then the program will be too machine dependent; too unchangeable; and
most important, too difficult to read. The computer profession has taken a long
time to realize that "clever tricks" and the "guess-what-this-code-does"
mentality is a loss in the long run. I would hope that the home computer
personality has examined our history and is willing to forego a relearning of
that experience. 

Certainly, we want our programs to run fast, but first they have to %3run%1!
The size of current %7m%1-computers puts  an premium on cleverness. That's
healthy, but don't misdirect it. The premium is on understanding not
trickery. Enough of this crap; it's time to replace exhortation
with exemplification.

.SS(Symbolic mathematics)
When we approach a contemporary calculator we expect to receive
answers to questions like⊗↓After "appropriate
encoding".← "What's %34+(2*2*3)+9%1?"
Some calculators can even answer questions like⊗↓After even
%2more%1 "appropriate encoding".←  "What's 
%3x%82%3#+#2xy#+y%82%1, when %3x%1 is %32%1 and %3y%1 is %33%1?"
However, if we were audacious enough to ask "What's %32x+y+3x%1?"
our trusty calculator would complain, even though a grade-school
person might very well respond "%35x+y%1".
Calculators have an irritating fascination with numbers; let's see
what we can do about that.

Rather than begin with the kinds of algebraic simplification
involved in our "%35x+y%1"-example, we jump in at the deep end and examine
a symbolic computation which is basic to a claculus course: differentiation.
Differentiation %2is%1 a symbolic operation; it operates on expressions and
produces expressions. Differentiation is also much easier to 
specify algorithmically than "simplification"; a "simplification" in one context
is a "complexification" in another. Is 
%34+y(4+y)%1  simpler than %34+4y+y%82%1  or %3(2+y)%82%1 or %34(1+y)+y%82%1?
We can find circumstances in which any one of these expressions is the 
appropriate "simplification" given that the expression combines with a 
larger expression. Differentiation is more clear-cut.

The differentiation algorithm is recursive; think about it.
The question of differentiating a sum is reduced
to the ability to differentiate each summand.  

.BEGIN TABIT3(20,38,49);CENTERIT;

\d[%3f + g%*]/d%3x%* = d%3f/%*d%3x + %*d%3g%*/d%3x.
.END
Similar relationships 
hold for products, differences, and powers.

  There must be some termination
conditions.
Differentiation of a variable, say %3x%*, with respect to %3x%* is defined to be 1;
differentiating a constant, or a variable not equal to %3x%* with
respect to %3x%* gives a result of zero.  

.GROUP
More generally, if %3u%* is a constant or a variable then:

.BEGIN TABIT2(20,30);
\d%3u%*/d%3x%* =\1 if %3x = u
\\%10 otherwise
.END
.APART


Given the basic structure of our differentiation algorithm, we must
discuss the class of polynomials which we wish to consider.
Though polynomials can be arbitrarily complex, involving the operations of addition,
multiplication, negation, and exponentiation,  their general format is very simple
if they are described in prefix notation where the operation 
precedes its
operands. We assume that binary plus, times, and exponentiation are 
symbolized by +, *, and ↑; we will
write %3+[x;2]%* instead of the usual infix notation  %3x+2%*.
We can be more specific about this class of polynomials:

.BEGIN INDENT 0,5;group;
%21.%*  constants and variables are terms.

%22.%*  If t%41%* and t%42%* are  terms then the "product" 
of t%41%* and t%42%* is a term.

%23.%*  If t%41%* is a variable and t%42%* is a constant then 
"t%41%* raised to the t%42%*%8th%1 power" is a term.

%24.%*  If t%41%* is a term then "minus" t%41%*  is a term.
.apart;
.GROUP;

and finally:

%25.%*  Any term is a polynomial.

%26.%*  If p%41%* and p%42%* are polynomials then the "sum"
of p%41%* and p%42%* is a polynomial.
.END

.APART
.GROUP;

We  now give a BNF description⊗↓Well, the secret's out: we expect to teach
you more  than just how to program in LISP. To only do that would be 
a disservice  both to you and LISP.← of the above set using 
the syntax of prefix notation:


.BEGIN TABIT1(13);GROUP;
<poly>\::= <term> | <plus>[<poly>;<poly>]
<term>\::= <constant> | <variable> | <times>[<term>;<term>] | <expt>[<variable>;<constant>]
\::= <minus><term>
<constant>\::= <numeral>  
<plus>\::= + 
<times>\::= * 
<expt>\::= ↑
<minus>\::= -
<variable>\::= <identifier>

.END
.APART;

As we have seen, it is easy to write recursive
algorithms in LISP; the only problem here is that the domain and
range of LISP functions is lists, not the polynomials.
We need  to represent arbitrary polynomials as lists.
.GROUP;
It simplify  discussions to add a bit of notation:
Let %eR%* be a function, mapping objects to their  representation. That
way we can simply write 
"%eR%f(%1<object>%f)%1" instead of "representation of <object>".
For example,
a variable is mapped to its uppercase counterpart in the 
vocabulary of LISP atoms. Thus:
.BEGIN CENTER;

%eR%f(%1<variable>%f)%1#=#<literal atom>.
.END
Let the representation of  numerals, be just the LISP numerals:
.BEGIN CENTER;

%eR%*%f(%1<numeral>%f)%1#=#<numeral>.
.END
.APART

We have now specified a representation for the base domains of the
 definition of our polynomials. At this point  we can develop the
termination cases for the recursive definition of differentiation.
We will represent the d-operator as a binary  LISP function named %3diff%*.
The application, d%3u%*/d%3x%* will be represented as %3diff[u;x]%*.
Since constants and variables are both represented as atoms,
we can check for both of these cases by using the predicate %3isindiv%*.
Thus a representation of the termination cases might be:

.BEGIN TABIT2(20,30);

\%3diff[u;x] <= [atom[u] → [eq[x;u] → 1; 0] ... ]%1#####⊗↓You 
should be a bit wary of our definition already: %3diff[1;1]%* will
evaluate  to %31%1.←
.END
.APART


Now that we have covered the termination case, we must handle the general
cases. This first involves extending %eR%1 to 
sums and products.
We will represent the operations *, +, -, and ↑ as atoms:

.BEGIN tabit2(15,40);GROUP;

\%eR%*%f(%1 + %f)%1 = %3PLUS%1\%eR%*%f(%1 - %f)%1 = %3MINUS%1
\%eR%*%f(%1 * %f)%1 = %3TIMES%1\%eR%*%f(%1 ↑ %f)%1 = %3EXPT%1
%1
.END

We will extend the mapping %eR%* to occurrences of binary operators by mapping
to three-element lists:

.BEGIN CENTERIT;
←%eR%*%f(%3 %9α%3[%9β%41%3;%9β%42%3] %f)%1 = %3(%eR%f(%9α%f)%3  %eR%f(%9β%41%f)%1  %eR%f(%9β%42%f)%3).
.END

.BEGIN CENTERIT; GROUP;

%1For example:←%eR%f(%3 +[x; 2] %f)%1 =  %3(PLUS X 2)%*.
.GROUP
A more complicated example: the polynomial,

%3←x%82%* + 2yz + u%1
.APART
will be translated to the  prefix notation:

%3←+[↑[x;2]; +[*[2;*[y;z]]; u]] %1.

From this it's easy to get the list form:
.NOFILL
%3

←(PLUS (EXPT X 2)  (PLUS (TIMES 2 (TIMES Y Z)) U))
%1
.FILL
%1
.BEGIN TABIT3(10,28,39);CENTERIT;
.FILL;
Now we can complete the differentiation algorithm for + and *.
We would see a sum
represented as:
.NOFILL;

←%3u = %eR%f(%3 f + g %f)%1  = %3(PLUS %eR%f(%3 f %f)%3 %eR%f( %3g %f)%3)%1

where:\%3second[u] = %eR%f( %3f %f)%1 and, %3##\third[u] = %eR%f(%3 g %f)%1.
.FILL
We have entered an unwise course here.
We have tied the algorithm for symbolic differentiation to a specific 
representation for polynomials. Believing that much can 
be learned from seeing mistakes, we will use that  representation, and
soon  we will examine our decision. 
.APART


.GROUP;
The result of differentiating %3u%* is to be a new list of three
elements:
.NOFILL

\1.  the symbol %3PLUS%*.
\2.  the effect of %3diff%* operating %eR%f( %3f %f)%1
\3.  the effect of %3diff%* operating %eR%f( %3g %f)%1
.APART

.GROUP
Thus another part of the algorithm:

%3
\eq [first[u];PLUS] →\list [PLUS; diff[second[u];x];diff[third[u];x]].
%1.


.APART
.GROUP;
.FILL
We know that
d[%3f*g]%*/d%3x%* is defined to be %3f* %1d%3g%*/d%3x + g *%1d%*f/%1d%*x%1;
So here's another part of %3diff%*:
.NOFILL
%3

\eq[first[u];TIMES] →\list[PLUS; 
\\     list[TIMES; second[u];diff [third[u];x]];
\\     list[TIMES;third[u];diff [second[u];x]]]
%1
.APART

.GROUP;
We could put the pieces together in a nice %3if%1-expression:
.BEGIN TABs 10,12,14,16;turn on "\";nofill;

\%3if[\%1<termination test>%3;%1
\\%1<termination case>%3;%1
\\%3if[%1\<plus test>%3;%1
\\\<plus case>%3;%1
\\\%3if[%1\<times test>%3;%1
\\\\<times case>%3;%1
\\\\<error case>%3]]]
.END
.APART
.fill
That's kind of  cute; it lends itself to  "The Mouse's Tail"-programming.
It  %2does%1 have the misfortune of proliferating parentheses.
Therefore we propose an abbreviation, exending conditional expressions
to handle several cases within a level. We will abbreviate:
.nofill
.BEGIN TABs 10,12,14,16;turn on "\";nofill;

\%3if[\%1<predicate%41%1>%3;%1
\\%1<expression%41%1>%3;%1
\\%3if[%1\<predicate%42%1>%3;%1
\\\<expression%42%1>%3;%1
\\\      .   .   .
\\\%3if[%1\<predicate%4n-1%1>%3;%1
\\\\<expression%4n-1>%3;%1
\\\\<expression%4n%1>%3]...]]
.END
.BEGIN FILL;

%3[%1<predicate%41%1>%3 → %1<expression%41%1>%3;%1 <predicate%42%1>%3 → %1<expression%42%1>%3;%1
 ... %et%3 → %1<expression%4n%1>%3]%1

Notice that the %2last%1 <predicate> is %et%1; that's alright, since the
value of %et%1 is %et%1 --#a constant. It is common to read %et%1 
used in this
context as "otherwise".
.END

.GROUP
Using the extended conditional, here's the %3diff%1 algorithm for  + and *.
%3
.BEGIN TABIT3(14,37,41);

diff[u;x] <=\[isindiv[u] → [eq [x;u] → 1; %et%* → 0];
\ eq [first [u]; PLUS] → list\[PLUS; 
\\ diff [second [u]; x];
\\ diff [third [u]; x]];
\ eq [first[u]; TIMES] → list\[PLUS; 
\\ list\[TIMES; 
\\\ second[u];
\\\ diff [third [u]; x]];
\\ list\[TIMES; 
\\\ third [u];
\\\ diff [second[u]; x]]];
\ %et%* → %3error[%9'%3BAD_FOOD_FOR_DIFF]]
.END
.APART
.GROUP;fill
%1Before passing on, we should note that since
the extended conditional is to be used in our programming language, we
must supply a representation of it in list-notation. That we do:

.BEGIN TURN ON "←";
←%eR%f( %3[p%41%* → e%41%*; ... ;p%4n%* → e%4n%*] %f)%3 =
(%3COND%* %3(%eR%f(%3 p%41 %f)%3  %eR%f(%3 e%41%f)%3 ) ... (%eR%f(%3 p%4n%3 %f)%3 %eR%f(%3 e%4n %f)%3))
.END
Also the "otherwise case" contains an %3error%1-call; we will say more
about LISP's cleverness with errors later.
%1But now, here's an example. We know:###%3d[%3x*y + x]%*/d%3x = y + 1%1

.END
.GROUP
.BEGIN TABIT3(20,25,29);

Try:##%3diff [(PLUS (TIMES X Y) X); X]
\=list [PLUS; diff[(TIMES X Y); X]; diff [X;X]]
\=list [PLUS; 
\\list [PLUS; 
\\\list [TIMES; X; diff [Y;X]];
\\\list [TIMES; Y; diff [X;X]]];
\\diff [X;X]]

\=list [PLUS;
\\list [PLUS;
\\\list [TIMES; X ;0];
\\\list [TIMES; Y;1]];
\\1 ]

.APART
\=(PLUS  (PLUS (TIMES X 0) (TIMES Y 1)) 1)

.END
%1
which can be interpreted as:%3←x*0 + y*1 + 1 .
%1

Now it is clear that we have the right answer; it is equally clear that
the representation leaves much to be desired. There are obvious
simplifications which we would expect to have done before we would
consider this output acceptable. 

This example is a
particularly simple case for algebraic simplification. We can easily
write a LISP program to perform simplifications like those expected here:
like replacing %30*x%1 by %30%*, and %3x*1%* by %3x%*. But the general
problem of writing simplifiers, or indeed of recognizing 
what is a simplification, is quite difficult.
A whole branch of computer science has grown up around 
symbolic and algebraic manipulation of expressions. One of the
crucial parts of such an endeavor is a sophisticated simplifier.
For more details and examples of the power of such systems see
⊗↑[Hea#68]↑, ⊗↑[MAC#74]↑, or ⊗↑[Mos#74]↑.

.<<abstracting from rep>>
.GROUP;
.CENT(Points to note)

.SELECT 1;
This problem of representation is typical of data structure
algorithms regardless of what language you use.  That is,
once you have decided what the informal algorithm is, pick a
representation which makes your algorithms clean. Examine the interplay between
the algorithm and the representation, and continue to examine your decisions
as you refine your method.
.APART;

As we mentioned earlier, the current manifestation of %3diff%* encodes too
much of our particular representation for polynomials. The separation
of algorithm from representation is beneficial from at least two standpoints.
First, changing representation should have a minimal effect on the structure
of the algorithm, but %3diff%* %2knows%* that variables are represented as atoms
and a sum is represented as a list whose %3first%*-part is %3PLUS%*.
Second, readability of the algorithm suffers greatly.
How much of %3diff%* really needs to know about the representation and
how can we improve the readability of %3diff%*?

The uses of %3first%*, %3second%*, and %3third%* are not 
particularly mnemonic. That is, their names do not reflect the
%2intent%1 of the algorithm, the reflect this particular %2representation%1.
 We used
%3second%* to get the first argument to a sum or product and used %3third%*
to get the second.
We used %3first%* to extract the operator.
Let's try to replace these representation dependent names with terminology
with reflects more of the problem statement.

.GROUP;
Let's define the selectors:

.BEGIN CENTERIT;SELECT 3;group;
←op[x] <= first[x]
←arg%41%*[x] <= second[x]
←arg%42%*[x] <= third[x]
.END
.APART
.GROUP

Then %3diff%* becomes:

.BEGIN TABIT3(13,35,39);select 3;
.GROUP

diff[u;x] <=\[isindiv[u] → [eq [x;u] → 1; %et%* → 0];
\ eq [op[u]; PLUS] → list\[PLUS; 
\\ diff [arg%41%* [u]; x];
\\ diff [arg%42%* [u]; x]];
\ eq [op[u]; TIMES] → list\[PLUS; 
\\ list\[TIMES; 
\\\ arg%41%* [u];
\\\ diff [arg%42%* [u]; x]];
\\ list\[TIMES; 
\\\ arg%42%* [u];
\\\ diff [arg%41%* [u]; x]]];
\ %Et%* → error[]]
.APART
.END
.APART

Still, there is much of the representation present. Recognition of variables
and other terms can be abstracted. We need only
recognize when a term is a sum, a product, a variable or a constant.
  To test for the occurrence of a numeral we shall assume
a unary LISP predicate called %3numberp%* which returns %et%* just in the case
that its argument is a numeral.
Then,
in terms of the current  representation, we could define such recognizers and
predicates as:

.BEGIN CENTERIT; SELECT 3;group;tabit2(15,45)

\issum[x] <= eq[op[x];PLUS]\isprod[x] <= eq[op[x];TIMES]

\isconst[x] <= numberp[x]\samevar[x;y] <= eq[x;y]

←isvar[x] <= [isindiv[x] → not[isconst[x]]; %et%* → %ef%*]


.END
.GROUP;
Now we can rewrite %3diff%* as:

.BEGIN TABIT3(13,26,30);select 3;
.GROUP

diff[u;x] <= \[isvar[u] → [samevar[x;u] → 1; %et%* → 0];
\ isconst[u] → 0;
\ issum[u] → list\[PLUS; 
\\ diff [arg%41%*[u]; x];
\\ diff [arg%42%*[u]; x]];
\ isprod[u] → list\[PLUS; 
\\ list\[TIMES; 
\\\ arg%41%*[u];
\\\ diff [arg%42%*[u]; x]];
\\ list\[TIMES; 
\\\ arg%42%*[u];
\\\ diff [arg%41%*[u]; x]]];
\ %et%* → error[]]
.APART
.END
.APART;

Readability is certainly improving, but the representation is still
known to %3diff%*.
When we build the result of the sum or product of derivatives we use
knowledge of the representation.
It would be better to define:
.BEGIN  SELECT 3;group;tabit2(15,45)

\makesum[x;y] <= list[PLUS;x;y]\makeprod[x;y] <= list[TIMES;x;y]
.END
.GROUP;
Then the new %3diff%* is:

.BEGIN TABIT3(13,31,39);select 3;
.GROUP

diff[u;x] <=\[isvar[u] → [samevar[x;u] → 1; %et%* → 0];
\ isconst[u] → 0;
\ issum[u] → makesum[\diff[arg%41%*[u]; x];
\\diff[arg%42%*[u]; x]];
\ isprod[u] → makesum[\makeprod[\arg%41%*[u];
\\\diff[arg%42%*[u]; x]];
\\makeprod[\arg%42%*[u];
\\\diff [arg%41%*[u]; x]]];
\ %et%* → error[]]
.APART
.END
.APART

In the process,
%3diff%* has become much more understandable and, more importantly, the details
of the representation have been relegated to subfunctions. Changing
representation simply requires supplying different subfunctions. No changes
need be made to %3diff%*. There has only been a slight decrease in efficiency.
The termination condition in the original %3diff%* is a bit more succinct,
but incorrect.
Looking back, first we abstracted the selector 
functions: those which selected components; next we abstracted the recognizers:
the predicates indicating which term was present; finally we modified
the constructors: the functions which make new terms.

The %3diff%* algorithm is abstract now, in the sense that the representation
of the domain and the representation of the functions and predicates which
manipulate that domain have been extracted out. This is our %9r%*-mapping
again; we mapped the domain of <poly>'s to lists and mapped the
constructors, selectors, and recognizers to list-manipulating functions.
Thus the data types of the arguments %3u%* and %3x%* are <poly> and <var>
respectively, %2not%* list and atom. To  stress this point we should make one more
transformation on  %3diff%*. We have frequently said that there
is a substantial parallel between a data structure and the algorithms which
manipulate it. Paralleling the earlier BNF definition of <poly>, we 
write:

.BEGIN TABIT2(12,30);select 3;
.GROUP

diff[u;x] <=\[isterm[u] → diffterm[u;x];
\ issum[u] → makesum[\diff[arg%41%*[u]; x];
\\diff[arg%42%*[u]; x]];
\ %et%* → error[]]
.APART

.end
.BEGIN TABIT3(16,34,43);select 3;
.GROUP
diffterm[u;x] <=\[isconst[u] → 0;
\ isvar[u] → [samevar[x;u] → 1; %et%* → 0];
\ isprod[u] → makesum[\makeprod[\arg%41%*[u];
\\\diff[arg%42%*[u]; x]];
\\makeprod[\arg%42%*[u];
\\\diff[arg%41%*[u]; x]]];
\ %et%* → error[]]
.APART
.END

.GROUP;
To satisfy our earlier complaint that %3diff[1; 1]%1 gives a defined
result, we should also add:

.BEGIN TABIT2(10,22);SELECT 3;GROUP;

\diff%9'%*[u; x] <= [\isvar[x] → [ispoly[u] → diff[u; x]]; %et%3 → error[]]
.END
.APART

Finally, notice that our abstraction process has masked the order-dependence
of conditional expressions. Exactly one of the recognizers will be satisfied
by the form  %3u%*.


.END
In the future we will dispense with the development of abstract algorithms,
and will attempt to present the most abstract version (which we can think of)
which is consistent with the detail of implementation we are discussing.
Defining a compiler as
 "%3compile[program]#<=#generate_code[parse[program]]%1 is (usually) as 
unsatisfactory as a twenty-page machine language listing of a compiler.


****add parsing and simplification*****
.SS(Tree Searching)
All this symbolic math is interesting, but let's do something %2useful%1.
Let's play games.

A ubiquitous feature of sophisticated game playing is "a strategy".
In simple gamesmanship, e.g. tic-tac-toe, the strategy may be quite simple,
indeed easily computable.
In games like checkers and chess, the algorithmic approach is in for
tough sledding. The heart of much of this strategy formation is often
a tree structure.  That tree will have nodes representing "possible moves".
In a single-person game, the  evaluation of the tree will result in
a "best move"; any move that wins. In a two-person game we must be more careful;
the branching structure will represent %2both%1 your moves and those
of the jerk you're playing, and the position evaluation must
take that into account: "Now if I move here, then  he'll screw me that
way,#...", etc.  We will consider both kinds of tree evaluations, and
following historical precedent, will present the simpler ones first.

LISP thinks highly of tree traversal  so,  without further ado,
let's assume that any node in a tree can have any finite
number of branches. We will also assume that the
trees will terminate on all of their branches.
That's enough information for the simple case; let's start naming the parts.
We'll have a tree, %3tr%1; associated with it will be a recognizer (remember
them?), named %3is_term%1, which will return %et%1 if the tree is the trivial
terminal tree  with no branches. A terminal tree may either be a %3WIN%1 or a 
%3LOSS%1. If it's a win, we know how to achieve our goal; if it's a 
%3LOSS%1, then we  look further. That "further" says examine the alternatives
of the immediately preceeding node; if there aren't any alternatives
then back up to %2its%1 predecessor.

Next, if a tree has branches we will select them with the selector %3branches%1;
not very original, but at least it's nmeumonic.

.BEGIN GROUP;SELECT 3;TABIT2(15,18);
eval_tree[tr] <= [\is_term[tr] → [is_win[tr] → tr; %et%3 → %3LOSS%1]
\%et%3 → eval_branches[branches[tr]]]

eval_branches[l] <= [\null[l] → LOSS;
\\eq[LOSS;eval_tree[first[l]]] → eval_branches[rest[l]];
\\%et%3 → first[l]]
.END
Not bad? We snuck in a few undefined LISP functions, but they should be clear
from context. What should be equally clear is the structure of the algorithm.
No reams of code, only two simple recursive definitions. You should also be
able to supply representations for  trees and therefore the selectors
and recognizers. We gave a few hints when we used  %3first%1 and %3rest%1;
sure, that's representation dependent, but a natural representation
for trees is lists and since the tree evaluator is proceeding
sequentially (in a left-to-right depth-first fashion) there is no loss
of generality. Translate the algorithms to list notation; supply
the  missing selectors and recognizers (no constructors here), and, oh
yes, implement LISP; and the programs will run.

Let's go after bigger fish: two-person games. 
This type of game includes checkers and chess. Computers have had reasonable
success in the checkers domain, and are beginning to play passable
chess. A recent article, ⊗↑[Sug#77]↑, even addresses the feasibility of
home computer chess machines.

In the following discussions we will make several assumptions.
.BEGIN INDENT 0,2,2;GROUP;
%21.%1 Our opponent is as smart as we are. Obviously false, but
this assumption will  be reflected  by using  our evaluation function
in evaluating the posiitions of our opponent.

%22.%1 As we said earlier, we must 
assume that our opponent is also trying to win. Therefore his move will
reflect his attempt to do us maximal harm, trying to mix up our
winning strategy. Since we are using the same position-evaluator,
his "maximal harm" is our "minimal good".
We are thus following a "max-min" strategy 
 wherein we attempt to find the best move
which our opponent cannot turn into    a disaster  for us. 
.END

From these ideas we formulate our position evaluation strategy as follows:
.BEGIN INDENT 0,2,2;
%21.%1. Grow a tree of moves. First our possible moves from a position, then
his counter moves; then our responses,#... Continue this until the
branch terminates or until we get tired⊗↓We assume we have  methods for 
determining when a move is already present in the tree.←. 

%22.%1 Once the tree is built, we evaluate the terminal nodes.

%23.%1 The values are propagated back up the tree using the min-max idea.
If the preceding node is ours, we assign that node the maximum of the
branch values; if the preceding node is his we assign the minimum of the
values. We proceed in this fashion, finally returning the value of the
"best path".
.END

We will simplify matters somewhat, returning only the "value" of the
best path, leaving the player in a state of fury since we won't tell
him how we found that path⊗↓Here's a hint on how to fix this
omission: bring back %2two%1 values.←. First we develop some  subfunctions:

.BEGIN group;select 3;turn off "∞";tabit1(32);
maxlist[l;f] <= [null[l] → -∞; %et%3 → max[\f[first[l]];
\maxlist[rest[l];f]]

minlist[l;f] <= [null[l] →  ∞; %et%3 →  min[\f[first[l]];
\minlist[rest[l];f]]
.END
Now before you go into trauma, we should explain  a few things.
First, the "%3∞%1" means "giant number, bigger than any other value
our evaluation function %3f%1 can concoct. Ok, but
what does the "%3f%1" mean?
It's a different kind of variable from that we have seen before.
It is used as a LISP function within the bodies of the definition, yet we
know that the arguments to LISP functions must be lists; tough. That's one of the
benefits of  the LISP  programming language; in the programming language, 
%2everything%1 is a list, so passing a (representation of a) function in as a 
parameter is no problem. Eat your heart out FORTRAN and BASIC.
In  the next article we will discuss the implementation of such LISP
niceties, but for now the intent should be clear. For example:

.BEGIN CENTER;SELECT 3;
maxlist[(1 3 5 2);add1] = 6 %1and%3  minlist[(1 3 5 2);add1] = 2.
.END
With those preliminaries, here's min-max.

.BEGIN SELECT 3; GROUP;
maxpos[p] <= [is_term[p] → value[p]; %et%3 → maxlist[branches[p]; minpos]]

minpos[p] <= [is_term[p] → value[p]; %et%3 → minlist[branches[p]; maxpos]]
.END
%3maxpos%1 gives the  value of a position for the maximizing player
and %3minpos%1 gives the  value of a position for the minimizing player.
##%3value%1 is the terminal position evaluation function. Neat, huh?

What's even more interesting is that there is a simple technique which
will allow us to discover the optimal path  usually without having to
visit all the nodes. The technique, discovered by John McCarthy in 1958,
is called  %7a%2-%7b%2#pruning%1; it is based on the observation that
if  our opponent is assured that he can force us into an unfavorable position
then he won't make a move with would give us a %2better%1 position.
That's obvious; what is %2not%1 obvious is that he can 
often make such decisions
on the basis of only a partial evaluation of the tree.
Consider:
.BEGIN SELECT g;NOFILL;PREFACE 0 MILLS;GROUP;
.TURN OFF "%","#";
.TURN ON "∞" FOR "%";
             O
             ~
      ⊂αααααα∀ααααα⊃	opponent∞1'∞gs moves
      ~            ~
      N            M
  ⊂αααβααα⊃    ⊂αααβαα ...⊃    our moves
  ~   ~   ~    ~
  7   3   4    ?    ... 
.END

Since we are to evaluate the position at %gN%1, we maximize the  position,
getting %g7%1; that becomes the value of node %gN%1. It is up to our
opponent to evaluate position %gO%1, and he now knows we're going to
get a %g7%1 if he moves to %gN%1. He looks questioningly at "?"; if that
value is greater than %g7%1 then he immediately rejects move %gM%1 without
examining the other possibilities; things can only get worse for him. 
If "?" is less than
%g7%1, then he looks at additional alternatives at %gM%1. Once our
opponent is finished evaluating the position,  then it's our turn
to play the game at the position above %gO%1, only now we will try to maximize
what that stingy individual has left us.
We let %7a%1 be the value which must be exceeded  for a position to be
desirable by the position about to play; and let %7b%1 be  the value which must
%2not%1 be exceeded if the move leading to the position would be make by the
opponent; in the above example %g7%1 is the %7b%1-value when evaluating
%gM%1. Enough; let's modify the min-max algorithms to include %7a%1-%7b%1
pruning.
.BEGIN group;select 3;turn off "∞";tabit2(21,33);

maxlist%4αβ%3[l;f;%7a%3;%7b%3] <= [\null[l] → %7a%3; 
\f[first[l]] %a≥%1 %7b%3 → %7b%3;
\%et%3 → maxlist%4αβ%3[\rest[l];
\\f;
\\max[%7a%3;f[first[l]]];
\\%7b%3]]

minlist%4αβ%3[l;f;%7a%3;%7b%3] <= [\null[l] → %7b%3; 
\f[first[l]] %a≤%1 %7a%3 → %7a%3;
\%et%3 → minlist%4αβ%3[\rest[l];
\\f;
\\%7a%3; 
\\min[%7b%3;f[first[l]]]]]
.END
.BEGIN group;select 3;turn off "∞";tabit1(20);

maxpos%4αβ%3[p;%7a%3;%7b%3] <= [\is_term[p] → max[%7a%3;min[%7b%3;value[p]]; 
\%et%3 → maxlist%4αβ%3[branches[p]; minpos%41%3;%7a%3;%7b%3]]

minpos%41%3[x] <= minpos%4αβ%3[x;%7a%3;%7b%3]

minpos%4αβ%3[p;%7a%3;%7b%3] <= [\is_term[p] → max[%7a%3;min[%7b%3;value[p]]; 
\%et%3 → minlist%4αβ%3[branches[p]; maxpos%41%3;%7a%3;%7b%3]]

maxpos%41%3[x] <= maxpos%4αβ%3[x;%7a%3;%7b%3]


.END
The process can be initialized with %7a%1 and %7b%1 set to %3-∞%1 and %3∞%1
respectively. Tighter bounds on "acceptablility" can be enforced by
picking different %7a%1's and %7b%1's. The effect will be to shorten the
search time will, perhaps ignoring some neat moves; %3caveat emptor%1.

This %2not%1 a trivial algorithm. However its  description as a LISP 
program is about as simple and as compact as you will find; anywhere.
.SS(Operating Systems and Language Systems)
Lisp is as good a "systems programming language" as mathematics is
a "numerical programming language". In algebra, when you write "%3x+y%1"
you do not expect to be asked "are %3x%1  and %3y%1 fixed or floating?".
Such a question would generate strange glances from many mathematically
inclined people. The point is that you can look on mathematics and LISP
as notational systems, independent of their possible computer applications.
A notational system must excell in freedom of expression, even at the
risk of  allowing a person to express nonsense; a programming system
should concern itself with the problems of efficiency but that should be a
quite separate issue. That is the point of type declarations in a language;
that added information will aid   the language processor in producing
better code or even checking the consistency of program segments. But the
notation is independent of such mundane matters.

This section will discuss several aspects of LISP which fall roughly
into the operating system area. This will involve discussion of the building
blocks as well as the actual language sub-system components like
editors and debuggers.
Though we will put off a full discussion of editing  and debugging
programs until 
a later article, we can  give a flavor of the "life-support" systems
which LISP users have come to expect.
We have touted  the program/data duality as an essential difference
between LISP and other "high-level" languages;  we have yet to demonstrate 
the usefullness of this property. That we remedy now.

Most of a program's lifetime is spent being a data structure. That means
the program is lying around being operated on by some other active element.
If that is so, then representing programs as data structures which are
easily manipulated such be of primary concern to language designers.
Let's examine the validity of the claim and then discuss some of the
benefits. First, when a program is under construction it is a data structure;
we are doing text construction and modification. When a program is being
compiled  it is a data structure; in traditional languages,
the external form  of the program is translated into an internal
tree-form⊗↓Called LISP.←, and that tree structure  is traversed to
produce code.  "Ah, Ha!" you exclaim, when we run that code the program
is %2not%1 a data structure. Quite true, but programs %2never%1 run; we
all know that they have bugs are need to be extended to new applications.
What happens? We through away the code and go back to the data structure,
and start the cycle all over again. How quaint. Tony Hoare
once said something to the effect that a good language designer would
rather avoid a problem rather than solve it. LISP is very good; it
ignores as many problems as possible. Translating from external form
to tree-form --#called parsing#-- is a non-trivial problem for most languages;
indeed, many compiler writers become so emamoured with the problem that they
forget that there's any thing more to do. LISP ignores the problem; a LISP 
parser (as well shall see) is quite trivial. Debugging compiled code can be
quite painful; relating low-level error symptoms with high-level source
statements requires good karma. LISP ignores that problem too; since
the program is available as a data structure, we need only write another
LISP program to monitor the behavior of the errant LISP program and
let us know when specified anomalies occur. The problem of correcting
bugs once they have been isolated is typically painful; execution must
be aborted and the original text modified. Again, since the LISP
program %2is%1 a data structure, another LISP program called an editor
can correct the damage and most LISP systems, the execution can 
be reset to an earlier point and continued. 

LISP is interactive. You create LISP programs like you drive a car.
Your program is not built and then thrown into a meat-grinder to
succeed or fail. Parts are built interactively an incrementally.
LISP programming style is best characterized as middle-out rather than
top-down or bottom-up.

****editor as subst***

****do plists*** 

***hint about rplaca/d****
.SS(Data Bases)

just poor os's (w.o. procedures in base)

.SEC(OUTLINE)
.BEGIN "VERB" VERBATiM
      I
Introduction
  machine orientation
  0.DISTINGUISH BETWEEN LISP AS a language (m-exprs)
       and a lisp machine (S-exprs)
  1. high level
  2. implementation

general characterisitics
 prog = data
 interactive ability
 examples of debugging and editing
 applications
       II
applications  and simple debugging and editing
introduce abstraction
     III
evaluation
  eval and freinds
  prog as extension
  assignment and rplaca-d

lambda's 
      IV
implementation of the static structurre
for ... machine
gc
hash
read
print
      V
dynamic strucutre
compilers
editors
debuggers
true interaction(??)
      VI
theory and advanced topics
abstraction using dotted pairs
proofs
equivalence and correctness
funargs and non-recursive eval
godel numbering and s-exprs
ai languages
.END "VERB"